#include <iostream>
#include <vector>
#include <queue>
#include <Vector.hpp>
using namespace std;


//BUG 加入优先队列的数据,可能在后续被更新,但是队列不会主动响应,考虑把时间数据一并存入,并剔除旧版本的时间
class Solution
{
private:
    struct Node
    {
        int minTime = -1;
        std::vector<std::pair<int, int>> connections;
    };

    struct CompareNode
    {
        const std::vector<Node> &nodeInfoes;

        CompareNode(const std::vector<Node> &nodeInfoes) : nodeInfoes(nodeInfoes) {}

        bool operator()(int a, int b) const
        {
            return nodeInfoes[a].minTime > nodeInfoes[b].minTime;
        }
    };

public:
    vector<int> minimumTime(int n, vector<vector<int>> &edges, vector<int> &disappear)
    {
        std::vector<Node> nodeInfoes(n);
        for (auto edge : edges)
        {
            if (edge[0] == edge[1])
                continue;
            nodeInfoes[edge[0]].connections.push_back(std::pair(edge[1], edge[2]));
            nodeInfoes[edge[1]].connections.push_back(std::pair(edge[0], edge[2]));
        }

        // start bfs
        CompareNode compare(nodeInfoes);
        std::priority_queue<int, std::vector<int>, CompareNode> activeNodeList(compare);
        activeNodeList.push(0);
        nodeInfoes[0].minTime = 0;
        while (!activeNodeList.empty())
        {
            int currentNode = activeNodeList.top();
            activeNodeList.pop();
            int currentMin = nodeInfoes[currentNode].minTime;
            for (auto connection : nodeInfoes[currentNode].connections)
            {
                if (currentMin + connection.second < disappear[connection.first] && (nodeInfoes[connection.first].minTime == -1 || currentMin + connection.second < nodeInfoes[connection.first].minTime))
                {
                    nodeInfoes[connection.first].minTime = currentMin + connection.second;
                    activeNodeList.push(connection.first);
                }
            }
        }
        std::vector<int> result(n);
        for (int i = 0; i < n; i++)
        {
            result[i] = nodeInfoes[i].minTime;
        }
        return result;
    }
};
int main()
{
    cout << "Code3112" << endl;
    Solution s;
    // std::vector<vector<int>> edges = {{0, 1, 2}, {1, 2, 1}, {0, 2, 4}};
    // std::vector<int> disappear = {1, 1, 5};
    // std::vector<int> disappear = {1, 3, 5};
    // std::vector<vector<int>> edges = {{2, 0, 6}, {1, 2, 1}, {2, 3, 1}, {0, 3, 3}};
    // std::vector<int> disappear = {19, 6, 9, 7, 17, 18};
    // auto result = s.minimumTime(6, edges, disappear);
    // std::vector<vector<int>> edges = {
    //     {4, 4, 1},
    //     {7, 4, 1},
    //     {5, 0, 5},
    //     {1, 7, 8},
    //     {2, 5, 2},
    //     {5, 5, 7},
    //     {7, 0, 8},
    //     {4, 0, 2}};
    // std::vector<int> disappear = {3, 19, 1, 1, 17, 5, 1, 11};
    // auto result = s.minimumTime(8, edges, disappear);
    std::vector<vector<int>> edges = {{5, 0, 1}, {3, 1, 9}, {0, 4, 2}, {5, 3, 9}, {1, 5, 6}, {1, 4, 3}, {1, 2, 4}, {3, 0, 7}};
    std::vector<int> disappear = {11, 18, 14, 20, 17, 20};
    auto result = s.minimumTime(6, edges, disappear);
    PrintVector(result);
    return 0;
}